package com.zjj.lbw.algorithm.sort;

import java.util.Arrays;

/**
 * @author zhanglei.zjj
 * @description 归并排序
 * @date 2023/3/28 22:21
 */
public class MergeSort {
    public static void main(String[] args) {
        int[] unsortedArr = new int[]{35, 63, 48, 9, 86, 24, 53, 72};
        System.out.println("排序前元素顺序为：" + Arrays.toString(unsortedArr));
        int[] sortedArr = mergesort(unsortedArr);
        System.out.println("排序后元素的顺序为：" + Arrays.toString(sortedArr));
    }

    static int[] mergesort(int[] arr) {
        if (arr.length > 2) {
            int childArrLength = (arr.length % 2 == 0) ? (arr.length / 2) : (arr.length/2 + 1);
            int[] leftArr = new int[childArrLength];
            int[] rightArr = new int[childArrLength];
            for (int i = 0; i < arr.length; i++) {
                if (i < childArrLength) {
                    leftArr[i] = arr[i];
                } else {
                    rightArr[i - childArrLength] = arr[i];
                }
            }
            System.out.println("本次拆分后左子表：" + Arrays.toString(leftArr));
            System.out.println("本次拆分后右子表：" + Arrays.toString(rightArr));

            int[] leftSortedArr = mergesort(leftArr);
            int[] rightSortedArr = mergesort(rightArr);

            // 左右子序列合并
            int leftIndex = 0;
            int rightIndex = 0;
            int[] mergeArr = new int[leftSortedArr.length + rightSortedArr.length];
            int mergeIndex = 0;
            while (leftIndex < leftSortedArr.length || rightIndex < rightSortedArr.length) {
                if (leftIndex == leftSortedArr.length) {
                    mergeArr[mergeIndex++] = rightSortedArr[rightIndex++];
                    continue;
                }
                if (rightIndex == rightSortedArr.length) {
                    mergeArr[mergeIndex++] = leftSortedArr[leftIndex++];
                    continue;
                }
                if (leftSortedArr[leftIndex] > rightSortedArr[rightIndex]) {
                    mergeArr[mergeIndex++] = rightSortedArr[rightIndex++];

                } else {
                    mergeArr[mergeIndex++] = leftSortedArr[leftIndex++];
                }
            }
            return mergeArr;
        }
        if (arr.length == 1) {
            return arr;
        }
        // 因为只有两个元素，可以直接比大小 然后交换即可
        if (arr[0] > arr[1]) {
            int temp = arr[0];
            arr[0] = arr[1];
            arr[1] = temp;
        }

        return arr;
    }
}
